В реальном мире очень часто встречаются задачи удовлетворения ограничений с непрерывными областями определения, и эти задачи интенсивно изучаются в области исследования операций. Например, для планирования экспериментов на космическом телескопе Хаббл требуется очень точная привязка наблюдений по времени; начало и конец каждого наблюдения и каждого маневра представляют собой переменные со значениями из непрерывной области определения, которые должны подчиняться всевозможным астрономическим ограничениям, ограничениям предшествования и ограничениям по мощности двигателей. Одной из широко известных категорий задач CSP с непрерывной областью определения являются задачи линейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область. Задачи линейного программирования могут быть решены за время, которое зависит полиномиально от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций — задачи квадратичного программирования, конического программирования второго порядка и т.д.

Кроме исследования типов переменных, которые могут присутствовать в задачах CSP, полезно заняться изучением типов ограничений. Простейшим типом ограничения является унарное ограничение, которое ограничивает значение единственной переменной. Например, может оказаться, что жители штата Южная Австралия очень не любят зеленый цвет, {green}. Каждое унарное ограничение можно устранить, выполняя предварительную обработку области определения соответствующей переменной, чтобы удалить любое значение, нарушающее это ограничение. Бинарное ограничение связывает между собой две переменные. Например, бинарным ограничением является. Бинарной задачей CSP называется задача, в которой предусмотрены только бинарные ограничения; она может быть представлена в виде графа ограничений, подобного приведенному на рис. 5.1,б.

В ограничениях высокого порядка участвуют три или больше переменных. Одним из известных примеров таких задач являются криптоарифметические головоломки, называемые также числовыми ребусами (рис. 5.2, а). Обычно предъявляется требование, чтобы каждая буква в криптоарифметической головоломке представляла отдельную цифру. В случае задачи, показанной на рис. 5.2, а, такое требование может быть выражено с помощью ограничения с шестью переменными . Иным образом это требование может быть представлено в виде коллекций бинарных ограничений, таких какОграничения сложения для четырех столбцов этой головоломки также включают несколько переменных и могут быть записаны следующим образом:

где x1,x2, и х3 — вспомогательные переменные, представляющие цифру (0 или 1), которая переносится в следующий столбец. Ограничения высокого порядка могут быть представлены в виде гиперграфа ограничений, подобного приведенному на рис. 5.2, б. Внимательный читатель заметит, что ограничение Alldiff может быть разбито на бинарные ограничения—и т.д. И действительно, в упр. 5.11 предлагается доказать, что каждое ограничение высокого порядка с конечной областью определения можно свести к множеству бинарных ограничений, введя достаточное количество вспомогательных переменных. В связи с этим в данной главе будут рассматриваться только бинарные ограничения.